package demo.practice.linklist;

import demo.practice.ListNode;

public class P61 {

    /**
     旋转链表
     输入：head = [1,2,3,4,5], k = 2
     输出：[4,5,1,2,3]

     提示：
     链表中节点的数目在范围 [0, 500] 内
     -100 <= Node.val <= 100
     0 <= k <= 2 * 10^9

     将倒数第k个位置的元素拿到最前面来作为头，头的前面是没有元素的，所以倒数第k个元素的next要置空
         1.倒数第k个元素的求法  已经有题  剑指 Offer 22     //其实可以求倒数第k+1个数
         2.Nk代表（倒数第k个节点）nodek.pre.next=null (Nk的前一个节点的next指针置空，避免成一个环形连表） 返回Nk个节点作为head节点  newhead=nodek
         tail.next=head

     这里还要注意 k的范围可能超过连表的长度，所以要先求连表的长度

     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {

        if(head==null)
            return null;
        int len=0;
        ListNode cur=head;
        ListNode tail=null;
        while (cur!=null){
            len++;
            tail=cur;
            cur=cur.next;
        }


        //此时也恰好找到了末尾节点tail

        //求得链表的长度  len。移动len个距离，相当于在原地，所以k=k%len
        k=k%len;
        //这里已经求出了len了，就不用再用  剑指 Offer 22的双指针了
        if(k==0)
            return head;//不需要旋转

        cur=head;
        int count=len-k-1;
        while ( cur!=null && count>0  ){
            count--;
            cur=cur.next;
        }

        tail.next=head;
        ListNode newHead=cur.next;
        cur.next=null;
        return newHead;
    }
}
